home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / impl / seg_tree.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  8.8 KB  |  318 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  seg_tree.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_SEGMENT_TREE_H
  17. #define LEDA_SEGMENT_TREE_H
  18.  
  19. // ------------------------------------------------------------------
  20. //
  21. // full dynamic Segment Trees
  22. //
  23. // Michael Wenzel     (1990)
  24. //
  25. // Implementation follows
  26. // Kurt Mehlhorn: Data Structures and Algorithms, Vol. 3
  27. //
  28. // ------------------------------------------------------------------
  29.  
  30. #include <LEDA/impl/bb_tree1.h>
  31. #include <LEDA/list.h>
  32.  
  33. // ------------------------------------------------------------------
  34. // declarations and definitions 
  35. // ----------------------------------------------------------------- 
  36.  
  37.  
  38. class h_segment;
  39. typedef h_segment* h_segment_p;
  40.  
  41. class seg_node_tree;
  42. typedef seg_node_tree* seg_node_list;
  43.  
  44.  
  45. typedef bb_node* seg_tree_item;
  46. typedef list<seg_tree_item> list_seg_tree_item_;
  47.  
  48. //------------------------------------------------------------------
  49. // class h_segment
  50. //------------------------------------------------------------------
  51.  
  52. class h_segment {
  53.  
  54.   GenPtr _x0;
  55.   GenPtr _x1;
  56.   GenPtr _y;
  57.   GenPtr _inf;
  58.  
  59.  public:
  60.  
  61.  GenPtr& x0()    { return _x0;   }
  62.  GenPtr& x1()    { return _x1;   }
  63.  GenPtr& y()     { return _y;    }
  64.  GenPtr& info()  { return _inf;  }
  65.  
  66.  h_segment()
  67. { 
  68.    _x0 = _x1 = _y = _inf = 0;
  69.  }
  70.  
  71.  h_segment(GenPtr x0, GenPtr x1, GenPtr y, GenPtr i=0)
  72. { 
  73.    _x0  = x0;
  74.    _x1  = x1;
  75.    _y   = y;
  76.    _inf = i;
  77.  }
  78.  
  79.  LEDA_MEMORY(h_segment)
  80.  
  81.  friend ostream& operator<<(ostream&, h_segment&);
  82.  friend class Segment_Tree;
  83.  friend class seg_node_tree;
  84.  
  85. };
  86.  
  87.  
  88. /*------------------------------------------------------------------
  89.    class seg_node_tree = Dictionary(seg_tree_item , void* )
  90. -------------------------------------------------------------------*/
  91.  
  92. class seg_node_tree : public bb_tree {
  93.  
  94. public:
  95.  
  96. Segment_Tree* father;
  97.  
  98. int cmp(GenPtr x, GenPtr y) const;
  99.  
  100. list<seg_tree_item> query(GenPtr, GenPtr);
  101. list<seg_tree_item> all_items();
  102.  
  103. int            defined(h_segment_p y)    { return bb_tree::member(Convert(y)); }
  104. seg_tree_item  lookup(h_segment_p y)     { return bb_tree::lookup(Convert(y)); }
  105. seg_tree_item  locate(h_segment_p y)     { return bb_tree::locate(Convert(y)); }
  106. seg_tree_item  ord(int y)                { return bb_tree::ord(int(y)); }
  107. seg_tree_item  insert(h_segment_p y, GenPtr i=0 )
  108.                                  { return bb_tree::insert(Convert(y),i); } 
  109. void del(h_segment_p y)          { delete bb_tree::del(Convert(y)); } 
  110. void del_item(seg_tree_item it)  { del(key(it)); } 
  111.  
  112. h_segment_p& key(seg_tree_item it)   
  113.          { if (!it) error_handler(1,"seg_tree_item gleich nil");
  114.                return (h_segment_p&)it->ke  ; }
  115. GenPtr&   info(seg_tree_item it)              { return key(it)->info(); } 
  116. void         change_inf(seg_tree_item it, GenPtr i) { key(it)->info() = i; }
  117.  
  118. seg_node_tree(Segment_Tree* p)   {father = p;}
  119. virtual ~seg_node_tree()  {}
  120.  
  121. friend class Segment_Tree;
  122.  
  123. } ;
  124.  
  125.  
  126. #define forall_seg_tree_items(a,b) for ((b).init_iterator(); a=(b).move_iterator(); )
  127.  
  128.  
  129.  
  130. //------------------------------------------------------------------
  131. // class segment_tree
  132. //------------------------------------------------------------------
  133.  
  134. class Segment_Tree  : public bb_tree {
  135.  
  136.  
  137. virtual  h_segment_p new_y_h_segment(GenPtr y)
  138. { cout << "error: virtual new_y_h_segmentn"; y=0; return 0; }
  139.  
  140. virtual int cmp_dim1(GenPtr x,GenPtr y) {return compare(x,y);}
  141. virtual int cmp_dim2(GenPtr x,GenPtr y) {return compare(x,y);}
  142.  
  143. virtual void clear_dim1(GenPtr&) {}
  144. virtual void clear_dim2(GenPtr&) {}
  145. virtual void clear_info(GenPtr&) {}
  146. virtual void copy_dim1(GenPtr&)  {}
  147. virtual void copy_dim2(GenPtr&)  {}
  148. virtual void copy_info(GenPtr&)  {}
  149.  
  150. int seg_cmp(h_segment_p p, h_segment_p q);
  151.  
  152.   void lrot(bb_item , bb_item);
  153.   void rrot(bb_item , bb_item);
  154.   void ldrot(bb_item , bb_item);
  155.   void rdrot(bb_item , bb_item);
  156.  
  157.   //void change_inf(bb_item it, seg_node_list i)   { info(it) = i; }
  158.  
  159.   GenPtr& key(bb_item it)       
  160.        { if (!it) error_handler(1,"bb_item in segment_tree gleich nil");
  161.      return it->ke; }
  162.   seg_node_list& info(bb_item it)    { return (seg_node_list&)(bb_tree::info(it)); } 
  163.  
  164.   int start_coord(bb_item& x,seg_tree_item& i)
  165.       { return (!cmp(key(x),x0(i))); }
  166.   int end_coord(bb_item& x,seg_tree_item& i)
  167.       { return (!cmp(key(x),x1(i))); }
  168.  
  169.   int empty(bb_item);
  170.   void clear(bb_item& );
  171.   void print(bb_item , string); 
  172.  
  173.   protected:
  174.  
  175.   seg_node_tree r;                // tree with all segments
  176.  
  177.  
  178.   int cmp_dummy(int a, int b, int c);
  179.  
  180.  
  181.   public :
  182.   
  183.   int cmp(GenPtr, GenPtr)  const    
  184.   { cout << "error: Segment_Tree::cmpn"; return 0; }
  185.  
  186.   GenPtr x0(seg_tree_item x)    { return (r.key(x))->_x0;  }
  187.   GenPtr x1(seg_tree_item x)    { return (r.key(x))->_x1;  }
  188.   GenPtr y(seg_tree_item x)     { return (r.key(x))->_y;   }
  189.   GenPtr& inf(seg_tree_item x)  { return r.info(x);        }
  190.  
  191.   GenPtr& x0(h_segment_p x)   { return x->_x0; }
  192.   GenPtr& x1(h_segment_p x)   { return x->_x1; }
  193.   GenPtr& y(h_segment_p x)    { return x->_y; }
  194.   GenPtr& inf(h_segment_p x)  { return x->_inf; }
  195.  
  196.   void change_inf(seg_tree_item x, GenPtr i)  { r.info(x) = i; }
  197.  
  198.   seg_tree_item insert(GenPtr, GenPtr, GenPtr, GenPtr i=0 );
  199.  
  200.   void del(GenPtr, GenPtr, GenPtr);
  201.   void del_item(seg_tree_item it) { del(x0(it),x1(it),y(it)) ; }
  202.  
  203.  
  204.   seg_tree_item lookup(GenPtr, GenPtr, GenPtr );
  205.   int member(GenPtr x0, GenPtr x1, GenPtr y) { return (lookup(x0,x1,y)!=0 ) ; }
  206.  
  207.   list<seg_tree_item> query(GenPtr, GenPtr, GenPtr );
  208.   list<seg_tree_item> x_infinity_query(GenPtr, GenPtr );
  209.   list<seg_tree_item> y_infinity_query(GenPtr );
  210.   list<seg_tree_item> all_items();
  211.  
  212.   void clear_tree();  
  213.  
  214.    Segment_Tree();
  215.    virtual ~Segment_Tree();
  216.  
  217.   int size()                   { return r.size();   }
  218.   int empty()                  { return (r.size()==0) ; }
  219.  
  220.   seg_tree_item y_min()        { return r.min();    }
  221.   seg_tree_item y_max()        { return r.max();    }
  222.  
  223.   void init_iterator()            { r.init_iterator(); }
  224.   seg_tree_item move_iterator()   { return r.move_iterator(); }
  225.  
  226.   void print_tree()               { print(root,"");    }
  227.  
  228.  
  229.   friend class seg_node_tree;
  230.  
  231. };
  232.  
  233.  
  234. //------------------------------------------------------------------
  235. // typed segment_tree
  236. //------------------------------------------------------------------
  237.  
  238.  
  239.  
  240. template <class  type1, class type2, class itype>
  241.  
  242. class _CLASSTYPE segment_tree : public Segment_Tree {
  243.  
  244. h_segment_p new_y_h_segment(GenPtr y)
  245. { type1 x1; type2 x2;
  246.   Init(x1); Init(x2);
  247.   return new h_segment(Copy(x1),Copy(x2),y);
  248.  }
  249.  
  250. int cmp_dim1(GenPtr x,GenPtr y)
  251. { return compare(ACCESS(type1,x),ACCESS(type1,y)); }
  252.  
  253. int cmp_dim2(GenPtr x,GenPtr y)
  254. { return compare(ACCESS(type2,x),ACCESS(type2,y)); }
  255.  
  256. void clear_dim1(GenPtr& x)     { Clear(ACCESS(type1,x)); }
  257. void clear_dim2(GenPtr& x)     { Clear(ACCESS(type2,x)); }
  258. void clear_info(GenPtr& x)     { Clear(ACCESS(itype,x)); }
  259.  
  260. void copy_dim1(GenPtr& x)     { x=Copy(ACCESS(type1,x)); }
  261. void copy_dim2(GenPtr& x)     { x=Copy(ACCESS(type2,x)); }
  262. void copy_info(GenPtr& x)     { x=Copy(ACCESS(itype,x)); }
  263.  
  264. int cmp(GenPtr x, GenPtr y) const
  265. { return compare(ACCESS(type1,x),ACCESS(type1,y));}
  266.  
  267. public:
  268.  
  269. type1  x0(seg_tree_item it)  { return ACCESS(type1,Segment_Tree::x0(it)); }
  270. type1  x1(seg_tree_item it)  { return ACCESS(type1,Segment_Tree::x1(it)); }
  271. type2   y(seg_tree_item it)  { return ACCESS(type2,Segment_Tree::y(it));  }
  272. itype inf(seg_tree_item it)  { return ACCESS(itype,Segment_Tree::inf(it));}
  273.  
  274. seg_tree_item insert(type1 x0, type1 x1, type2 y, itype i)
  275. { return Segment_Tree::insert(Convert(x0),Convert(x1),Convert(y),Convert(i)); }
  276.  
  277. void del(type1 x0, type1 x1, type2 y)
  278. { Segment_Tree::del(Convert(x0),Convert(x1),Convert(y)); }
  279.  
  280. seg_tree_item lookup(type1 x0, type1 x1, type2 y)
  281. { return Segment_Tree::lookup(Convert(x0),Convert(x1),Convert(y)); }
  282.  
  283. int member(type1 x0, type1 x1, type2 y)
  284. { return Segment_Tree::member(Convert(x0),Convert(x1),Convert(y)); }
  285.  
  286. list<seg_tree_item> query(type1 x,type2 y0,type2 y1)
  287. { return Segment_Tree::query(Convert(x),Convert(y0),Convert(y1)); }
  288.  
  289. list<seg_tree_item> x_infinity_query(type2 y0,type2 y1)
  290. { return Segment_Tree::x_infinity_query(Convert(y0),Convert(y1)); }
  291.  
  292. list<seg_tree_item> y_infinity_query(type1 x)
  293. { return Segment_Tree::y_infinity_query(Convert(x)); }
  294.  
  295.  
  296. segment_tree()  {}
  297. ~segment_tree()
  298.  { seg_tree_item z;
  299.   forall_seg_tree_items(z,r)
  300.   { type1 t1 = x0(z); Clear(t1); 
  301.           t1 = x1(z); Clear(t1); 
  302.     type2 t2 = y(z);  Clear(t2); 
  303.     itype i  = inf(z); Clear(i); 
  304.     delete r.key(z); }
  305.  }
  306.  
  307. } ;
  308.  
  309.  
  310. //------------------------------------------------------------------
  311. // Iterator
  312. //------------------------------------------------------------------
  313.  
  314. #define forall_seg_tree_items(a,b) for ((b).init_iterator(); a=(b).move_iterator(); )
  315.  
  316.  
  317. #endif
  318.